package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 113.路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的【路径】
 */
public class BiTree16_PathSum {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, null, 5, 1);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 二叉树路径总和
        System.out.println(pathSum(root, 22));
    }

    // 符合条件的叶子节点路径列表
    static List<List<Integer>> resultList = new ArrayList<>();
    // 叶子节点路径
    static List<Integer> pathList = new ArrayList<>();

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return resultList;
        }
        traversal2(root, targetSum);
        return resultList;
    }

    // 回溯
    private static void traversal(TreeNode root, int targetSum) {
        // 将当前节点添加到路径中
        pathList.add(root.val);
        // 如果当前节点为叶子节，再判断路径节点值之和和目标值
        if (root.left == null && root.right == null) {
            if (targetSum - root.val == 0) {
                resultList.add(new ArrayList<>(pathList));
            }
        }
        if (root.left != null) {
            traversal(root.left, targetSum - root.val);
        }
        if (root.right != null) {
            traversal(root.right, targetSum - root.val);
        }
        // 回溯，移除当前节点
        pathList.remove(pathList.size() - 1);
    }

    // 回溯：简写版，将判空放到前面，减少对空节点的不必要的操作
    private static void traversal2(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        // 将当前节点的值添加到路径中，并从 targetSum 中减去当前节点的值
        pathList.add(root.val);
        // targetSum -= root.val;
        // 如果当前节点为叶子节，再判断路径节点值之和和目标值
        if (root.left == null && root.right == null) {
            // 路径中的节点值之和正好等于目标值，则将此路径添加到结果列表中
            if (targetSum - root.val == 0) {
                resultList.add(new ArrayList<>(pathList));
            }
        }
        // 递归遍历左子树和右子树，继续寻找符合条件的路径
        traversal2(root.left, targetSum - root.val);
        traversal2(root.right, targetSum - root.val);
        // 回溯，重复利用 pathList
        pathList.remove(pathList.size() - 1);
    }

}
